package com.acwing.partition4;

import java.io.*;

/**
 * @author `RKC`
 * @date 2022/1/16 14:40
 */
public class AC343排序 {

    private static final int N = 26;
    private static int[][] graph = new int[N][N], dist = new int[N][N];
    private static boolean[] visited = new boolean[N];

    private static int n = 0, m = 0;

    private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        while (true) {
            String[] s = reader.readLine().split("\\s+");
            n = Integer.parseInt(s[0]);
            m = Integer.parseInt(s[1]);
            if (n == 0 && m == 0) break;
            reset();
            int judge = 0, cnt = 0;
            for (int i = 1; i <= m; i++) {
                String str = reader.readLine();
                int u = str.charAt(0) - 'A', v = str.charAt(2) - 'A';
                if (judge == 0) {
                    graph[u][v] = 1;
                    floyd();
                    judge = check();
                    if (judge != 0) cnt = i;
                }
            }
            //返回0表示目前的条件不足够判断出来顺序，返回2表示存在至少一个冲突的条件，返回1表示有唯一的情况确定顺序
            if (judge == 0) writer.write("Sorted sequence cannot be determined.\n");
            else if (judge == 2) writer.write(String.format("Inconsistency found after %d relations.\n", cnt));
            else {
                //能唯一的确定各个点之间的关系，每次输出没访问过的最小的点
                writer.write(String.format("Sorted sequence determined after %d relations: ", cnt));
                for (int i = 0; i < n; i++) writer.write(getMin());
                writer.write(".\n");
            }
        }
        writer.flush();
    }

    private static void reset() {
        for (int i = 0; i < N; i++) {
            visited[i] = false;
            for (int j = 0; j < N; j++) {
                graph[i][j] = dist[i][j] = 0;
            }
        }
    }

    private static void floyd() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) dist[i][j] = graph[i][j];
        }
        //floyd传递连通性
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dist[i][j] |= dist[i][k] & dist[k][j];
                }
            }
        }
    }

    private static int check() {
        //dist[i][j]=1表示i<j，如果dist[i][i]=1，则表示i==i
        for (int i = 0; i < n; i++) {
            if (dist[i][i] != 0) return 2;
        }
        //要么i->j，要么j->i，否则就还不能确定
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (dist[i][j] == 0 && dist[j][i] == 0) return 0;
            }
        }
        return 1;
    }

    private static char getMin() {
        for (int i = 0; i < n; i++) {
            if (visited[i]) continue;
            //要满足当前点i比所有的其它点j小
            boolean flag = true;
            for (int j = 0; j < n; j++) {
                if (!visited[j] && dist[j][i] > 0) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                visited[i] = true;
                return (char) ('A' + i);
            }
        }
        return ' ';
    }
}
